package com.algorithm;

import java.util.HashMap;
import java.util.Map;

public class InsertSort {
    public static void main(String[] args) {
        int[] arr = new int[]{3, 5, 15, 32, 19, 36, 28, 44, 47, 50, 2};
       // new InsertSort().wordPattern("abba","dog cat cat fish");
       // System.out.println(new InsertSort().canWinNim(6));
       System.out.println( new InsertSort().firstUniqChar("cc"));
    }

    private void insertionSort(int[] arr) {
        int preIndex,current;
        //未排序的队列
        for (int i = 1; i < arr.length; i++) {
            //已排序的队列
            preIndex = i-1;
            current = arr[i];
            while(preIndex>=0 && arr[preIndex]>current){
                arr[preIndex+1] = arr[preIndex];
                preIndex -- ;
            }
            arr[preIndex+1] = current;
        }

        for (int a:arr) {
            System.out.print(a);
        }
        System.out.println();
    }

    private void mergeSort(int[] arr){
        int[] temp = new int[arr.length];
        mergeSort(arr,0,arr.length-1,temp);
    }

    private void mergeSort(int[] arr,int left,int right,int[] temp){
        if(left>=right){
            return ;
        }

        int mid = (left+right)/2 ;
        mergeSort(arr,left,mid,temp);
        mergeSort(arr,mid+1,right,temp);
        merge(arr,left,mid,right,temp);
    }

    private void merge(int[] arr,int left,int mid,int right,int[] temp){
        int i = left ;//左序列
        int j = mid+1;//右序列
        int t = 0 ;
        while(i<=mid && j<=right){
            temp[t++] = arr[i++]>arr[j++]?arr[j]:arr[i];
        }
        while(i<=mid){
            temp[t++] = arr[i++];
        }

        while(j<=right){
            temp[t++] = arr[j++];
        }

        t = 0 ;
        while(left<=right){
            arr[left++] = temp[t++];
        }
    }


    public boolean wordPattern(String pattern, String str) {
        String[] strs = str.split(" ");
        if(pattern==null){
            return false ;
        }

        if(pattern.length() != strs.length){
            return false ;
        }

        Map<Character,String> keyMap = new HashMap<Character,String>();
        Map<String,Character> valueMap = new HashMap<String,Character>();
        for(int i=0;i<pattern.length();i++){
            char a = pattern.charAt(i);
            if(!keyMap.containsKey(a)){
                keyMap.put(a,strs[i]);
            }else if(!keyMap.get(a).equals(strs[i])){
                return false ;
            }

            if(!valueMap.containsKey(strs[i])){
                valueMap.put(strs[i],a);
            }else if(valueMap.get(strs[i])!= a){
                return  false;
            }
        }
        return true ;
    }

    public String reverseVowels(String s) {
        if(s==null || s.length()==0){
            return s;
        }
        char[] chars = s.toCharArray();
        int beg = 0,end=chars.length-1;
        while(beg<end){
            char left = chars[beg];
            char right = chars[end];
            if(isVowel(left) && isVowel(right)){
                char a = chars[beg];
                chars[beg] = chars[end];
                chars[end]= a;
                beg++;
                end -- ;
            }else if(!isVowel(left)){
                beg++;
            }else{
                end -- ;
            }
        }
        return new String(chars);
    }

    private boolean isVowel(char a){
        return a=='a'||a=='A'||a=='e'||a=='E'||a=='i'||a=='I'||a=='o'||a=='O'||a=='u'||a=='U' ;
    }

    public boolean isPerfectSquare(int num) {
        int beg=0;
        int end = num;
        while(beg<=end){
            int mid = (end-beg)/2+beg ;
            int square = mid*mid ;
            if(square == num){
                return  true ;
            }

            if(isSquareOverflow(mid)){
                end = mid -1 ;
            }else{
                beg = mid+1 ;
            }
        }
        return false ;
    }
    private boolean isSquareOverflow(int mid){
        if(mid>Integer.MAX_VALUE/mid){
            return true;
        }else{
            return false ;
        }
    }

    public boolean canConstruct(String ransomNote, String magazine) {
        int[] source = new int[26];
        for(int i=0;i<magazine.length();i++){
            source[magazine.charAt(i)-'a'] ++ ;
        }

        for(int i=0;i<ransomNote.length();i++){
            if(--source[ransomNote.charAt(i)-'a']<0) {
                return false ;
            }
        }
        return true ;
    }

    public int firstUniqChar(String s) {
        if(s==null || s.length()==0){
            return -1 ;
        }
        int len = s.length();
        int beg = 0 ;
        boolean loop = false ;
        while(beg<len){
            loop = false ;
            for(int j=beg+1;j<len;j++){
                char a = s.charAt(j);
                if(s.charAt(beg) == a){
                    loop = true ;
                    break;
                }
            }
            if(loop){
                beg ++ ;
            }else{
                return beg ;
            }
        }
        int[] aa = new int[10] ;
        return -1 ;
    }
}
